package com.rfs.suanfa;

/**
 * @author renfushuai
 * @date 2022/2/8
 */
public class 删除链表的倒数第N个节点 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tempList = new ListNode();
        tempList.next = head;
        int listLen = 0;
        while (tempList.next != null) {
            listLen++; // 计算链表长度
            tempList = tempList.next;
        }
        ListNode resNode = new ListNode();
        resNode.next = head;
        int count = 1;
        while (true) {
            if (n == listLen) {  //如果是第一个节点
                resNode.next = head.next;
                break;
            } else if (count == listLen - n) { // 找到倒数第n个节点
                head.next = head.next.next;// 删除倒数第n个节点
                break;
            }
            head = head.next;//移动head
            count++;
        }
        return resNode.next;
    }
    /**
    * @author: rfs
    * @create: 2022/2/9
    * @description: 快慢指针
    **/
    public ListNode removeNthFromEnd_Slow_Fast(ListNode head,int n){
        ListNode temp = new ListNode();
        temp.next=head;
        ListNode fast=temp;
        ListNode slow=temp;
        while (n-->=0){
            fast=fast.next;
        }
        while (fast != null) {
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return temp.next;
    }
}
